use std::collections::hash_map::DefaultHasher;
use std::hash::{Hash, Hasher};

pub type SetValue<T> = Box<T>;

/// A single entry in the set.
struct SetEntry<T> {
    data: SetValue<T>,
    next: Option<Box<SetEntry<T>>>,
}

/// The main Set structure.
pub struct Set<T: Eq + Hash> {
    table: Vec<Option<Box<SetEntry<T>>>>,
    entries: usize,
    table_size: usize,
    hash_func: fn(&T) -> u64,
    equal_func: fn(&T, &T) -> bool,
}

impl<T: Eq + Hash> Set<T> {
    /// Create a new set with a given hash and equality function.
    pub fn new(hash_func: fn(&T) -> u64, equal_func: fn(&T, &T) -> bool) -> Self {
        let initial_size = 193; // Start with a prime table size
        let table = vec![];
        Set {
            table,
            entries: 0,
            table_size: initial_size,
            hash_func,
            equal_func,
        }
    }

    /// Insert a value into the set.
    pub fn insert(&mut self, data: T) -> bool {
        let hash = (self.hash_func)(&data);
        let index = (hash % self.table_size as u64) as usize;

        let mut current = &mut self.table[index];
        while let Some(entry) = current {
            if (self.equal_func)(&entry.data, &data) {
                return false; // Value already exists
            }
            current = &mut entry.next;
        }

        // Insert the new value
        let new_entry = Box::new(SetEntry {
            data: Box::new(data),
            next: self.table[index].take(),
        });

        self.table[index] = Some(new_entry);
        self.entries += 1;

        // Resize if load factor exceeds threshold
        if self.entries * 3 > self.table_size * 2 {
            self.resize();
        }

        true
    }

    /// Remove a value from the set.
    pub fn remove(&mut self, data: &T) -> bool {
        let hash = (self.hash_func)(data);
        let index = (hash % self.table_size as u64) as usize;

        // 特殊处理链表头
        if let Some(entry) = &self.table[index] {
            if (self.equal_func)(&entry.data, data) {
                // 找到要删除的元素在链表头
                self.table[index] = self.table[index].take().unwrap().next;
                self.entries -= 1;
                return true;
            }
        }

        // 处理链表中的其他位置
        let mut current = &mut self.table[index];
        while let Some(entry) = current {
            // 查看下一个节点是否是要删除的元素
            if let Some(next_entry) = &entry.next {
                if (self.equal_func)(&next_entry.data, data) {
                    // 找到要删除的元素，更新链表连接
                    entry.next = entry.next.take().unwrap().next;
                    self.entries -= 1;
                    return true;
                }
            }
            current = &mut entry.next;
        }

        false
    }

    /// Query if a value exists in the set.
    pub fn contains(&self, data: &T) -> bool {
        let hash = (self.hash_func)(data);
        let index = (hash % self.table_size as u64) as usize;

        let mut current = &self.table[index];
        while let Some(entry) = current {
            if (self.equal_func)(&entry.data, data) {
                return true;
            }
            current = &entry.next;
        }

        false
    }

    /// Resize the hash table to accommodate more entries.
    fn resize(&mut self) {
        let old_table = std::mem::take(&mut self.table);
        self.table_size *= 2; // Double the size
        self.table = vec![];

        for mut entry in old_table.into_iter().flatten() {
            let hash = (self.hash_func)(&entry.data);
            let index = (hash % self.table_size as u64) as usize;

            entry.next = self.table[index].take();
            self.table[index] = Some(entry);
        }
    }

    /// Get the number of entries in the set.
    pub fn num_entries(&self) -> usize {
        self.entries
    }
}

/// Example hash function using Rust's DefaultHasher.
pub fn default_hash_func<T: Hash>(value: &T) -> u64 {
    let mut hasher = DefaultHasher::new();
    value.hash(&mut hasher);
    hasher.finish()
}

/// Example equality function.
pub fn default_equal_func<T: Eq>(a: &T, b: &T) -> bool {
    a == b
}

fn main() {}
